package LeetCode;

public class LongestSubstringWithoutRepeatingCharacters
{

  public int lengthOfLongestSubstring1(String s)
  {
    // Start typing your Java solution below
    // DO NOT write main() function
    int length = s.length();
    if (length <= 1) return length;
    int[] found = new int[26];
    int start = 0;
    int end = 0;
    int l = 0;
    while (start < length) {
      int c = s.charAt(start) - 'a';
      found[c]++;
      if (found[c] == 1) {
        int len = start - end + 1;
        if (len > l) l = len;
      }
      else {
        while (found[c] > 1 && end <= start) {
          int ec = s.charAt(end) - 'a';
          found[ec]--;
          end++;
        }
      }
      start++;
    }
    return l;
  }

  /*
   * Given a string, find the length of the longest substring without repeating
   * characters. For example, the longest substring without repeating letters
   * for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest
   * substring is "b", with the length of 1.
   */
  // pass both
  public int lengthOfLongestSubstring(String s)
  {
    // Start typing your Java solution below
    // DO NOT write main() function
    int visited[] = new int[26];
    /*
     * Initialize the visited array as -1, -1 is used to indicate that character
     * has not been visited yet.
     */
    for (int i = 0 ; i < 26 ; ++i)
      visited[i] = -1;

    int curr_length = 0;
    int max_length = 0;

    for (int i = 0 ; i < s.length() ; ++i) {
      int curr_index = s.charAt(i) - 'a';
      /*
       * If the current character is not present in the already processed
       * substring or it is not part of the current NRCS, then do cur_len++
       */
      if (-1 == visited[curr_index] || visited[curr_index] < i - curr_length) {
        ++curr_length;
      }
      /*
       * If the current character is present in currently considered NRCS, then
       * update NRCS to start from the next character of previous instance.
       */
      else {
        /*
         * Also, when we are changing the NRCS, we should also check whether
         * length of the previous NRCS was greater than max_len or not.
         */
        max_length = (max_length > curr_length)
                                               ? max_length
                                               : curr_length;
        curr_length = i - visited[curr_index];
      }
      // update the index of current character
      visited[curr_index] = i;
    }

    max_length = (max_length > curr_length)
                                           ? max_length
                                           : curr_length;

    return max_length;
  }

  /**
   * @param args
   */
  public static void main(String[] args)
  {
    // TODO Auto-generated method stub

  }

}
